﻿// Bridging signals POJ - 1631.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstring>
#include <stdio.h>

using namespace std;
//https://vjudge.csgrandeur.cn/problem/POJ-1631

/*
哦，不，他们又这样做了"，威化芯片厂的首席设计师喊道。路由设计人员又一次彻底搞砸了，使得芯片上连接两个功能块端口的信号到处交叉。
在工艺的后期阶段，重做布线的成本太高。相反，工程师们必须利用三维技术桥接信号，这样就不会出现两个信号交叉的情况。
然而，桥接是一项复杂的操作，因此希望桥接的信号越少越好。因此，急需一种计算机程序来找出硅表面上可连接而不会相互交叉的信号的最大数量。
考虑到一个功能块的边界可能有数千个信号端口，这个问题对程序员提出了很高的要求。你能胜任吗？

图 1 是一个典型的示意图。两个功能块的端口从上到下编号为 1 至 p。
信号映射由数字 1 到 p 的排列组合描述，其形式为 1 到 p 范围内 p 个唯一数字的列表，其中第 i 个数字指定右侧的哪个端口应连接到左侧的第 i 个端口。
输入
输入的第一行是一个正整数 n，表示后面要进行的测试的个数。
每个测试方案都以一行开始，其中包含一个正整数 p < 40000，即两个功能块的端口数。
然后是 p 行，描述信号映射：第 i 行是右侧功能块的端口号，应连接到左侧功能块的第 i 个端口。
输出
针对每种测试方案，输出一行，其中包含在硅表面布线而不会相互交叉的信号的最大数量。

4
6
4
2
6
3
1
5
10
2
3
4
5
6
7
8
9
10
1
8
8
7
6
5
4
3
2
1
9
5
8
9
2
3
1
7
4
6

3
9
1
4
*/

int t, p;
const int N = 40010;
int dp[N];
int line[N];

int bsearch(int v, int l, int r) {
	while (l < r) {
		int mid = (l + r) >> 1;
		if (dp[mid] >= v) {
			r = mid;
		}
		else {
			l = mid + 1;
		}
	}
	dp[l] = v;
	return l;
}

void solve() {
	//求最大上升子序列长度
	memset(dp, 0x3f, sizeof dp);
	int ans = 1;
	for (int i = 1; i <= p; i++) {
		int v = line[i];
		int pos = bsearch(v, 1, ans+1);
		ans = max(pos, ans);
	}

	printf("%d\n",ans);
	
	return ;
}


int main()
{
	//cin >> t;
	scanf("%d",&t);
	while (t--) {
		//cin >> p;
		scanf("%d",&p);
		for (int i = 1; i <= p; i++) {
			//cin >> line[i];
			scanf("%d",&line[i]);
		}
		solve();
	}


	return 0;
}

